1. Field of the Invention
The present invention generally relates to digital data processing circuits, and more particularly to a binary X+2X adder using a multi-bit generate/propagate circuit.
2. Background Description
Binary multipliers are generally used in microprocessors, digital signal processors, micro controllers, and other digital integrated circuit (IC) products. For multipliers which use a multi-bit Booth algorithm, dedicated 3X computation circuits are needed for partial product generation, and the 3X partial product generator is almost always on the critical timing path. Conceptually, multiplying an input X by 3 can be accomplished by adding the input X and its 1-bit left-shifted value 2X using an adder as illustrated in the table of FIG. 1.
In FIG. 1, the addend (X) represents a multi-bit 00x.sub.52. . . x.sub.i. . . x.sub.3 x.sub.2 x.sub.1 x.sub.0 binary number X, where x.sub.0 is the least-significant-bit. The augend (2x) represents a 1-bit left-shifted version of addend, which has a binary value of 2X. As in any type of adder design, the speed of the adder is often limited by the time it takes to perform carry generation and propagation logic delay. Therefore, any simplification of the carry generation and propagation logic for X+2X adder would directly improve the speed of 3X computation, and hence the speed of any given multiplier.
FIG. 2 represents a prior art generate/propagate circuit design for a X+2X adder. The first level of the carry-look-ahead tree are 2-bit generate/propagate circuits based on following logic equations: EQU g2.sub.1 =a.sub.i b.sub.i +a.sub.i-1 b.sub.i-1 (EQ 1) EQU p2.sub.i =(a.sub.i +b.sub.i) (a.sub.i-1 +b.sub.i-1) (EQ 2)
Equation 1 is implemented by two AND gates 101 and 102 and an OR gate 103, and equation 2 is implemented by two OR gates 104 and 105 and an AND gate 106. The next pair of significant bits a.sub.i-2, b.sub.i-2 and a.sub.i-3, b.sub.i-3 are operated on by similar logic, and so on. At the second level of the tree, 4-bit generate/propagate signals are produced by merging two adjacent 2-bit generate/propagate signals in a conventional approach, with the logic equations given by: EQU g4.sub.i =g2.sub.i +p2.sub.i g2.sub.i-2 (EQ 3) EQU p4.sub.i =g2.sub.i +p2.sub.i p2.sub.i-2 (EQ 4)
Equation 3 is implemented by OR gate 107 and AND gate 108, and equation 4 is similarly implemented by OR gate 109 and AND gate 110. FIG. 3 is the truth table for the prior art 4-bit generate/propagate function implemented in the logic of FIG. 2.